#include <bits/stdc++.h>
#define rep(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define pre(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)
#define ull unsigned long long
#define int long long
using namespace std;
const int N = 400000 + 10;
struct node
{
	int sum;
	map<int, int>::iterator t;
}l[N], r[N];
struct segment
{
	int l, r;
	bool operator < (const segment &seg) const {
		if (r != seg.r) return r < seg.r;
		return l < seg.l;
	}
}q[N];
int n;
map<int, int> mp;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	freopen("kte.in", "r", stdin);
	freopen("kte.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		int x, res = 0; cin >> x;
		if (!mp[x]) mp[x] = 1, n++;
		else mp.erase(x), n--;
		rep(i, 1, n - 1)
		{
			if (i == 1)
			{
				auto it = mp.end();
				it--;
				r[i].sum = (*it).first;
				r[i].t = it;
				l[i].sum = (*mp.begin()).first;
				l[i].t = mp.begin();
			}
			else
			{
				auto it = l[i - 1].t;
				++it;
				l[i] = node{l[i - 1].sum + (*it).first, it};
				it = r[i - 1].t;
				--it;
				r[i] = node{r[i - 1].sum + (*it).first, it};
			}
			q[i] = segment{l[i].sum, r[i].sum};
		}
		sort (q + 1, q + n);
		int now = q[1].r, tl = q[1].l;
//		rep(i, 1, n - 1) cout << q[i].l << " " << q[i].r <<"\n";
		rep(i, 2, n - 1)
		{
			if (q[i].l > now)
			{
				res += now - tl;
				tl = q[i].l;
			}
			now = q[i].r; 
		}
		res += now - tl;
		cout << res << "\n";
	}
	return 0;
}

